package com.epam.training.collection;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<T> implements MyList<T>, MyStack<T>, MyQueue<T> {

	private int size;

	private Node<T> first;
	private Node<T> last;

	public MyLinkedList() {
		size = 0;
	}

	public MyLinkedList(MyList<T> c) {
		this();

		Iterator<T> itr = c.iterator();
		while (itr.hasNext()) {
			add(itr.next());
		}
	}

	public void addFirst(T e) {
		linkFirst(e);
	}

	/**
	 * Returns the first element in this list.
	 * 
	 * @return the first element in this list
	 */
	public T getFirst() {
		final Node<T> f = first;
		if (f == null) {
			throw new NullPointerException("No first element");
		}

		return f.element;
	}

	/**
	 * Returns the last element in this list.
	 * 
	 * @return the last element in this list
	 */
	public T getLast() {
		final Node<T> f = last;
		if (f == null) {
			throw new NullPointerException("No last element");
		}

		return f.element;
	}

	public void addLast(T e) {
		linkLast(e);
	}

	private void linkFirst(T e) {
		final Node<T> f = first;
		final Node<T> newNode = new Node<T>(null, e, first);

		first = newNode;

		if (f == null) {
			last = newNode;
		} else {
			f.previous = newNode;
		}

		size++;
	}

	private void linkLast(T e) {
		final Node<T> l = last;
		Node<T> newNode = new Node<T>(l, e, null);
		last = newNode;

		if (l == null) {
			first = newNode;
		} else {
			l.next = newNode;
		}

		size++;
	}

	public void add(T e) {
		linkLast(e);
	}

	public void add(T e, int index) {
		if (index == size) {
			linkLast(e);
		}

		Node<T> node = searchNode(index);
		final Node<T> prev = node.previous;
		final Node<T> newNode = new Node<T>(prev, e, node);
		node.previous = newNode;
		if (prev == null) {
			first = newNode;
		} else {
			prev.next = newNode;
		}

		size++;
	}

	public void addAll(T[] c) {
		for (int i = 0; i < c.length; i++) {
			linkLast(c[i]);
		}
	}

	public void addAll(int index, T[] c) {
		checkIndexPosition(index);

		Node<T> node = searchNode(index);
		Node<T> prev = node.previous;

		if (index == size) {
			addAll(c);
			return;
		}

		for (int i = 0; i < c.length; i++) {
			Node<T> newNode = new Node<T>(prev, c[i], null);

			if (prev == null) {
				first = newNode;
			} else {
				prev.next = newNode;
			}
			prev = newNode;
		}

		prev.next = node;
		node.previous = prev;

		size += c.length;
	}

	public T get(int index) {
		checkIndexPosition(index);

		Node<T> element = searchNode(index);

		return element.element;
	}

	private Node<T> searchNode(int index) {
		Node<T> element;

		if (index < (size / 2)) {
			element = first;
			for (int i = 0; i < index; i++) {
				element = element.next;
			}
		} else {
			element = last;
			for (int i = size - 1; i > index; i--) {
				element = element.previous;
			}
		}

		return element;
	}

	private void checkIndexPosition(int index) {
		if (index > size) {
			throw new MyIndexOutOfBoundsException("Index > size");
		}
	}

	private void unlinkElement(Node<T> el) {
		final Node<T> prev = el.previous;
		final Node<T> next = el.next;
		prev.next = next;

		el.previous = null;
		el.element = null;
		el.next = null;
	}

	public T remove(int index) {
		checkIndexPosition(index);

		Node<T> element = searchNode(index);

		T el = element.element;
		unlinkElement(element);

		size--;

		return el;
	}

	public T removeFirst() {
		if (first == null) {
			throw new NullPointerException();
		}

		final Node<T> f = first;
		T element = f.element;
		final Node<T> next = f.next;
		first = next;

		f.next = null;
		f.element = null;

		if (next == null) {
			last = null;
		} else {
			next.previous = null;
		}

		size--;

		return element;
	}

	public T removeLast() {
		if (last == null) {
			throw new NullPointerException();
		}

		final Node<T> l = last;
		final Node<T> prev = l.previous;
		last = prev;

		T element = l.element;
		l.previous = null;
		l.element = null;

		if (prev == null) {
			first = null;
		} else {
			prev.next = null;
		}

		size--;

		return element;

	}

	public void clear() {
		Node<T> f = first;

		while (f != null) {
			final Node<T> next = f.next;
			f.previous = null;
			f.element = null;
			f.next = null;
			f = next;
		}
		first = last = null;
		size = 0;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void set(int index, T e) {
		if (index > size) {
			throw new IndexOutOfBoundsException("Index > size");
		}

		Node<T> node = searchNode(index);
		node.element = e;
	}

	public int indexOf(T o) {
		int index = size - 1;

		if (o == null) {
			for (Node<T> i = last; i != null; i = i.previous) {
				if (i.element == null) {
					return index;
				}

				index--;
			}
		} else {
			for (Node<T> i = last; i != null; i = i.previous) {
				if (o.equals(i.element)) {
					return index;
				}

				index--;
			}
		}

		return -1;
	}

	public int size() {
		return size;
	}

	public Object[] toArray() {
		Object[] el = new Object[size];
		int index = 0;
		Node<T> f = first;

		while (f.next != null) {
			final Node<T> x = f.next;
			el[index] = f.element;
			index++;
			f = x;
		}

		el[index] = f.element;

		return el;
	}

	public Iterator<T> iterator() {
		return new MyIterator();
	}

	private class MyIterator implements Iterator<T> {

		private Node<T> lastReturned = null;
		private Node<T> next;
		private int nextIndex;

		MyIterator() {
			next = first;
		}

		public boolean hasNext() {
			return nextIndex < size;
		}

		public T next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			lastReturned = next;
			next = next.next;
			nextIndex++;

			return lastReturned.element;
		}

		public void remove() {
			if (lastReturned == null) {
				throw new IllegalStateException();
			}

			Node<T> nxt = lastReturned.next;
			unlinkElement(lastReturned);
			if (next == lastReturned) {
				next = nxt;
			} else {
				size--;
				nextIndex--;
			}

			lastReturned = null;
		}
	}

	public Iterator<T> descendingIterator() {
		return new MyDescendingIterator();
	}

	private class MyDescendingIterator implements Iterator<T> {

		private Node<T> lastReturned = null;
		private Node<T> next;
		private int nextIndex;

		MyDescendingIterator() {
			next = last;
			nextIndex = size;
		}

		public boolean hasNext() {
			return nextIndex > 0;
		}

		public T next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			lastReturned = next;
			next = next.previous;
			nextIndex--;

			return lastReturned.element;
		}

		public void remove() {
			if (lastReturned == null) {
				throw new IllegalStateException();
			}

			Node<T> prev = lastReturned.previous;
			unlinkElement(prev);
			if (next == lastReturned) {
				next = prev;
			} else {
				size--;
				nextIndex--;
			}

			lastReturned = null;
		}
	}

	private static class Node<T> {

		T element;
		Node<T> next;
		Node<T> previous;

		Node(Node<T> previous, T element, Node<T> next) {
			this.element = element;
			this.previous = previous;
			this.next = next;
		}
	}

	/**
	 * Pushes an item onto the top of this stack.
	 * 
	 * @param e
	 *            - the element to add
	 */
	public void push(T e) {
		addFirst(e);
	}

	/**
	 * Removes the object at the top of this stack and returns that object as
	 * the value of this function.
	 * 
	 * @return The object at the top of this stack
	 */
	public T pop() {
		return removeFirst();
	}

	/**
	 * Inserts the specified element into this queue if it is possible to do so
	 * immediately without violating capacity restrictions. When using a
	 * capacity-restricted queue, this method is generally preferable to add(E),
	 * which can fail to insert an element only by throwing an exception.
	 * 
	 * @param e
	 *            - the element to add
	 */
	public void offer(T e) {
		addLast(e);
	}

	/**
	 * Retrieves, but does not remove, the head of this queue, or returns null
	 * if this queue is empty.
	 */
	public T peek() {
		return (first == null) ? null : first.element;
	}

	/**
	 * Retrieves and removes the head of this queue, or returns null if this
	 * queue is empty.
	 * 
	 * @return the head of this queue, or null if this queue is empty
	 */
	public T poll() {
		return (first == null) ? null : removeFirst();
	}

}
